package main.滑动窗口;

import java.util.*;

/**
 * @author tmh
 * @date 2024/7/10 11:42
 * @description
 * // https://leetcode.cn/problems/find-all-anagrams-in-a-string/solutions/9749/hua-dong-chuang-kou-tong-yong-si-xiang-jie-jue-zi-/?envType=study-plan-v2&envId=top-100-liked
 * 这个题解的思路真的好，我们的区间是一个左闭右开的区间[left,right)
 * 1. window:保存区间里面存在于p字符串里面的元素的个数
 * 2. need存储p字符串里面每个字符存在的个数
 * 3. valid，该变量表示 window中保存的元素个数和need中的该元素的个数相同的时候，该元素在区间里面有效
 */

//相当于，输入一个串 S，一个串 T，找到 S 中所有 T 的排列，返回它们的起始索引。

public class T438找到字符串中所有字母异位词 {
    public static void main(String[] args) {
        String s = "EBBANCF";
        String p = "ABC";
        findAnagrams(s, p);
    }

    //熟悉之后直接默写就行
    public static List<Integer> findAnagrams(String s, String p) {
        //定义一个List保存起始索引的结果
        List<Integer> result = new ArrayList<>();
        //定义一个window来保存窗口里面包含的p里面的字符的值，和 一个保存字符串p里面各个字符的map
        Map<Character, Integer> window = new HashMap<>();
        Map<Character, Integer> need = new HashMap<>();

        //定义一个valid，该变量表示 window中保存的元素个数和need中的该元素的个数相同的时候，该元素再区间有效
        int valid = 0;
        //把p里面的字符，放入need里面 ==>初始化p
        for (int i = 0; i < p.length(); i++) {
            Integer count = need.getOrDefault(p.charAt(i), 0);
            count += 1;
            need.put(p.charAt(i), count);
        }

        int right = 0, left = 0;
        //开始对字符串s进行一个遍历，我们的滑动窗口的区间是左闭右开的区间
        while (right < s.length()) {
            //保存当前的字符
            char c = s.charAt(right);
            //right++ ==> 更新区间里面的数据
            right++;
            //更新区间的数据
            if (need.containsKey(c)) {
                //把c放入window里面
                window.put(c, window.getOrDefault(c, 0) + 1);
                //再判断window里面的这个字符出现的次数和need里面这个字符出现的个数是否相同，相同的
                //话则就valid++，代表则个字符再窗口里面出现的次数满足p里面的要求
                if (window.get(c).equals(need.get(c))) {
                    valid++;
                }
            }
            //判断左面的窗口是否要收缩
            while (right - left >= p.length()) {
                //当窗口里面的元素符合条件的时候，就把left加入result里面
                if (valid == need.size()) {
                    result.add(left);
                }
                //获取left这个位置的值
                char d = s.charAt(left);
                //移动left，缩小窗口
                left++;
                //更新window里面的数据
                //输入: s = "abab", p = "ab"
                //输出: [0,1,2]
                if (need.containsKey(d)) {
                    //再来判断更新window之前d元素的个数和need里面d元素的个数是否相同，是的话就有效值-1
                    if (window.get(d).equals(need.get(d))) {
                        valid--;
                    }
                    //把window里面这个数出现的次数-1
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        return result;
    }
}
